#include <vector>
#include <iostream>
#include <deque>
#include <string>

using namespace std;

class Solution {
public:
    /**
     * 返回git树上两点的最近分割点
     * 
     * @param matrix 接邻矩阵，表示git树，matrix[i][j] == '1' 当且仅当git树中第i个和第j个节点有连接，节点0为git树的跟节点
     * @param indexA 节点A的index
     * @param indexB 节点B的index
     * @return 整型
     */
    int getSplitNode(vector<string> matrix, int indexA, int indexB) {
        this->size = matrix[0].size();
        //节点中有一个为根节点
        if(!indexA || !indexB)
            return 0;
        //自己跟自己
        if(indexA == indexB)
            return indexA;
        createTable(matrix);
        vector<int> pathA = createPath(indexA);
        vector<int> pathB = createPath(indexB);
        return findFirstCommon(pathA,pathB);
    }
    // void printV(vector<int> &v)
    // {
    //     for(int i : v)
    //         cout<<i<<',';
    //     cout<<endl;
    // }
    int findFirstCommon(vector<int> pathA,vector<int> pathB)
    {
        int del;
        // printV(pathA);
        // printV(pathB);
        if(pathA.size() > pathB.size())
        {
            del = pathA.size() - pathB.size();
            pathA.erase(pathA.begin(),pathA.begin() + del);
        }
        else
        {
            del = pathB.size() - pathA.size();
            if(del != 0)
                pathB.erase(pathB.begin(),pathB.begin() + del);
        }
        // printV(pathA);
        // printV(pathB);
        for(int i = 0 ; i < pathA.size() ; ++ i)
            if(pathA[i] == pathB[i])
                return pathA[i];
        return 0;
    }
    //构建节点到根路径
    vector<int> createPath(int index)
    {
        vector<int> rtn;
        while(index)
        {
            rtn.push_back(index);
            index = father[index];
        }
        rtn.push_back(0);
        return rtn;
    }
    //构建父节点数组
    void createTable(const vector<string> &matrix)
    {

        father.resize(size,0);
        deque<int> queue;
        queue.push_back(0);
        while(!queue.empty())
        {
            int pre = queue.front();
            int ex = father[pre];
            queue.pop_front();
            for(int i = 0 ; i < size ; ++i)
                if(i != ex && matrix[pre][i]=='1')
                {
                    father[i] = pre;
                    queue.push_back(i);
                }
        }
    }
private:
    int size;
    vector<int> father;
};


int main()
{
    Solution s;
    vector<string> vTest;
    // string s1("0100000");
    // string s2("1010000");
    // string s3("0100011");
    // string s4("0000001");
    // string s5("0000001");
    // string s6("0010000");
    // string s7("0011100");
    // vTest.push_back(s1);
    // vTest.push_back(s2);
    // vTest.push_back(s3);
    // vTest.push_back(s4);
    // vTest.push_back(s5);
    // vTest.push_back(s6);
    // vTest.push_back(s7);
    // cout<<s.getSplitNode(vTest,2,3)<<endl; 
    vTest.push_back(string("01011"));
    vTest.push_back(string("10100"));
    vTest.push_back(string("01000"));
    vTest.push_back(string("10000"));
    vTest.push_back(string("10000")); 
    cout<<s.getSplitNode(vTest,1,2)<<endl;

    return 0;
}